import java.util.*;

/**
 * 207. 课程表
 * https://leetcode-cn.com/problems/course-schedule/
 */
public class Solutions_207 {
    public static void main(String[] args) {
        int numCourses = 2;
        int[][] prerequisites = {{1, 0}};  // output: true

//        int numCourses = 2;
//        int[][] prerequisites = {{1, 0}, {0, 1}};  // output: false

        boolean result = canFinish(numCourses, prerequisites);
        System.out.println(result);
    }

    /**
     * 广度优先搜索-bfs
     */
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        Queue<Integer> queue = new LinkedList<>();
        // needCount[1] = 1：学习课程 1 需要先完成 1 门课程
        int[] needCount = new int[numCourses];

        // list.get(0).add(1)，完成课程 0 后，可以学习课程 1
        List<List<Integer>> list = new ArrayList<>(numCourses);
        for (int i = 0; i < numCourses; i++) {
            list.add(new ArrayList<>());
        }

        for (int[] arr : prerequisites) {
            // arr[0] 需要先完成的课程数量加 1
            needCount[arr[0]] ++;
            list.get(arr[1]).add(arr[0]);
        }
        for (int i = 0; i < numCourses; i++) {
            if (needCount[i] == 0) {
                // 记录下不需要先修其他课程的课程，入度为 0 的课程
                queue.add(i);
            }
        }
        if (queue.isEmpty()) {
            return false;
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                // 能够学完的课程减 1
                numCourses --;
                int j = queue.poll();
                List<Integer> ok = list.get(j);
                for (int k : ok) {
                    // 完成课程 j 后，需要完成课程 j 的那些课程的需要完成课程数量减 1
                    needCount[k] --;
                    if (needCount[k] == 0) {
                        // k 课程可以学习了
                        queue.add(k);
                    }
                }
            }
        }
        // 最终，numCourses 个课程都能够学完，return true
        return numCourses == 0;
    }
}
